A database is a collection of stored data that is logically related and that is accessible by one or more users. A popular type of database is the relational database management system (RDBMS), which includes relational tables made up of rows (or tuples) and columns (or attributes). Each row represents an occurrence of an entity defined by a table, with an entity being a person, place, or thing about which the table contains information.
With advances in database technology, increasingly complex types of data can be efficiently stored in database systems. Examples of complex types of data include spatial data, image data, audio data, video data, and so forth. There are several different types of spatial data. As examples, geographic applications and graphics design involve two-dimensional data. Geological applications and imaging applications involve three-dimensional data. In certain other applications, representation in four dimensions is needed, such as the representation of moving three-dimensional objects.
A challenge that has faced developers of database systems is providing a representation of spatial data that enables efficient database operations, such as joins. Various techniques have been developed, with one example technique based on z-ordering. Z-ordering approximates a given object geometry by recursively decomposing a data space into smaller subspaces, referred to as z-regions or z-cells. Z-ordering allows multiple resolution levels where a single spatial object can be composed of z-regions of varying resolution. Also, sets of spatial objects can be composed of regions of varying resolution. This enables the ability to efficiently manage sets of spatial objects of varying size.
Conventional z-ordering techniques decompose spatial objects into z-ordered regions using a top-own approach in which each spatial object is recursively decomposed from larger regions to smaller regions until some decomposition goal is achieved. Examples of such decomposition goals include error-based, size-bound, and granularity-bound goals. The error-bound goal defines a certain fixed accuracy (e.g., distance between object boundary and approximating geometry) that when reached causes decomposition to stop. The size-bound goal defines a maximum number of z-regions with which to approximate a spatial object. The granularity-bound goal causes decomposition to occur until a certain finest granularity (maximum number of decompositions or maximal resolution) is achieved.
The top-down approach has several drawbacks. Decomposing small spatial objects using the top-down technique can be costly in terms of computing resources since the top-down decomposition approach requires “contains” and “overlaps” comparisons for each element in the recursive descent. Contains and overlaps refer to the geometric relationship between z-ordered regions and portions of the spatial object. Also, because of the random nature in which z-ordered regions are chosen to represent a spatial object, optimal assignment of the spatial object to the z-ordered regions may not be accomplished.